package trees;

class Tree<T extends Comparable<T>> {
	Tree<T> left, right;
	T data;

	public Tree(T t) {
		this.data = t;
	}

	public static<T extends Comparable<T>> boolean insert(Tree<T> root, T t) {
		
		boolean added = false;
		if(find(root, t) == null) {
			
			Tree<T> tree = root;
			while (!added) {
				if (tree.data.compareTo(t) > 0) {
					if(tree.left == null) {
						tree.left = new Tree<T>(t);
						added = true;
						break;
					}
					tree = tree.left;
				} else {
					if(tree.right == null) {
						tree.right = new Tree<T>(t);
						added = true;
						break;
					}
					tree = tree.right;
				}
			}
		}

		return added;
	}

	public static<T extends Comparable<T>> Tree<T> remove(Tree<T> root, T t) {

		Tree<T> result = root;
		if (find(root, t) != null) {
			
			Tree<T> parent = null;
			Tree<T> tree = root;
			while (tree.data.compareTo(t) != 0) {
				parent = tree;
				if(tree.data.compareTo(t) < 0) {
					tree = tree.right;
				} else {
					tree = tree.left;
				}
			}
			int numberOfLeafs = getNumberOfChilds(tree);
			if (numberOfLeafs == 0) {
				if(parent != null) {
					if (parent.left == tree) {
						parent.left = null;
					} else {
						parent.right = null;
					}
				} else {
					result = null;
				}
			} else if (numberOfLeafs == 1) {
				if(parent == null) {
					result = (tree.left != null) ? tree.left : tree.right;
				} else {
					if(parent.left == tree) {
						parent.left = (tree.left != null) ? tree.left : tree.right;
					} else {
						parent.right = (tree.left != null) ? tree.left : tree.right;
					}
				}
			} else {
				T value = removeSuccessor(tree, tree.right);
				tree.data = value;
				
			}
		}
		return result;
	}
	
	public static<T extends Comparable<T>> int getNumberOfChilds(Tree<T> node) {
		int result = (node.left != null) ? 1 : 0;
		result += (node.right != null) ? 1 : 0;
		
		return result;
	}
	
	
	
	public static<T extends Comparable<T>> T removeSuccessor(Tree<T> parentTree, Tree<T> tree) {
		
		while(tree.left != null) {
			parentTree = tree;
			tree = tree.left;
		}
		if(parentTree.left == tree) {
			parentTree.left = tree.right;
		} else {
			parentTree.right = tree.right;
		}
		return tree.data;
	}

	public static<T extends Comparable<T>> Tree<T> find(Tree<T> tree, T t) {

		if (tree != null) {

			if (tree.data.compareTo(t) == 0) {
				return tree;
			} else {
				return (tree.data.compareTo(t) == -1) ? find(tree.right, t)
						: find(tree.left, t);
			}
		}
		return null;
	}
}

public class BSTTree {
	
	public static void inOrder(Tree tree) {
		
		if (tree.left != null) {
			inOrder(tree.left);
		} 
		System.out.print(tree.data + " ");
		if (tree.right != null) {
			inOrder(tree.right);
		}
		
	}

	public static void main(String[] args) {

		System.out.println(new Integer(5).compareTo(Integer.valueOf(6)));
		
		Tree<Integer> tree = new Tree<Integer>(10);
		Tree.insert(tree, 1);
		Tree.insert(tree, 8);
		Tree.insert(tree, 3);
		Tree.insert(tree, 12);
		Tree.insert(tree, 15);
		Tree.insert(tree, 20);
		Tree.insert(tree, 40);
		Tree.insert(tree, 14);
		
		inOrder(tree);
		
		Tree<Integer> head = Tree.remove(tree, 10);//
		System.out.println();
		
		inOrder(head);
		
		System.out.println("\n" + head.data);
		
	}
}
